#load "lib.cmo"
open Format;;
open Lib;;
#directory "../lib";;
#directory "../include";;
#load "shared.cmo";;
#load "mpfi.cma";;
#load "mpfi_arith.cmo";;
#load "prover.cmo";;
#load "cfsqp.cma";;
open Shared;;
module I = Mpfi_arith.I;;
let p x = print_string (I.to_string x);;
#install_printer p;;
module H = Heap.MaxInt;;
module A = Array';;
module O = Ordered.Int;;
module R = Random;;

let heap = H.create() ;;

let ins_rand heap n = 
  for i = 0 to n-1 do 
    let k = R.int 100000 in
      ignore(H.insert heap (k,I.of_string (string_of_int k)))
  done;;

let remh heap n = 
  for i = 0 to n-1 do 
    ignore(H.extract_max heap)
  done;;

let test () = 
  let n = ref 0 in
    while true do
      ins_rand heap 100000;
      remh heap 100000;
      print_endline ("level: " ^ string_of_int !n);
      incr n;
      Gc.print_stat stdout
    done;;

while true do
  test()
done



let vs = map (fun _ -> H.mk_node (R.int 10000000) 7) (replicate () 100000)
let vs' = A.of_list vs

A.iter (H.insert heap) vs'
heap
H.increase_key heap vs'.(0) 1000
heap

let n = H.extract_max heap

H.set_prio vs'.(4) 111 
vs'
heap

heap
n

heap
H.increase_key heap vs'.(50000) 9999993


A.iter (H.insert heap) vs'
heap


time H.heapsort vs'
time sort vs


H.maximum heap
H.extract_max heap
heap

H.build vs'

vs'

H.size heap
H.maximum heap

H.insert heap vs'.(0)
heap
H.insert heap vs'.(1)
heap
H.insert heap vs'.(2)
heap
H.insert heap vs'.(3)
heap
H.insert heap vs'.(4)
heap

H.insert heap vs'.(5)
heap
H.insert heap vs'.(6)
heap
H.insert heap vs'.(7)
heap
H.insert heap vs'.(8)
heap
H.insert heap vs'.(9)
heap

H.insert heap vs'.(10)
heap
H.insert heap vs'.(11)
heap
H.insert heap vs'.(12)
heap
H.insert heap vs'.(13)
heap
H.insert heap vs'.(14)
heap
H.insert heap vs'.(15)
heap


H.insert heap (H.mk_node 100 "sean")
H.insert heap (H.mk_node 100 "bill")
heap

H.heapsort ns



let heap = H.build ns



#trace H.insert
#trace H.hinsert
#trace H.increase_key
#trace H.extract_max
#trace H.max_heapify
#trace H.shrink
#trace H.should_shrink
#remove_printer print'
#untrace_all 
